package com.faiz.algorithm;

import java.util.ArrayList;
import java.util.List;

public class TreeToDoubleLinkedList {
    public static BinaryTree treeToDoublyList(BinaryTree root) {
        //我的方法是使用一个list把中序遍历的每一个节点都加入进去，
        List<BinaryTree> nodeList = new ArrayList<>();
        middleOrderTraversal(nodeList, root);
        int length = nodeList.size();
        for (int i = 0; i < length; i++) {
            if (i == 0) {
                nodeList.get(i).left = nodeList.get(i + 1);
                nodeList.get(i).right = null;

            } else if (i == length - 1) {
                nodeList.get(i).left = null;
                nodeList.get(i).right = nodeList.get(i - 1);
            } else {
                nodeList.get(i).left = nodeList.get(i + 1);
                nodeList.get(i).right = nodeList.get(i - 1);
            }
        }
        System.out.println(nodeList);
        return nodeList.get(0);
    }

    public static void middleOrderTraversal(List<BinaryTree> nodeList, BinaryTree root) {
        if (root != null) {
            middleOrderTraversal(nodeList, root.left);
            nodeList.add(root);
            middleOrderTraversal(nodeList, root.right);
        }
    }
}
